<HTML>
<!--
  -- Copyright (c) 1996-1999
  -- Silicon Graphics Computer Systems, Inc.
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Silicon Graphics makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -- Copyright (c) 1994
  -- Hewlett-Packard Company
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Hewlett-Packard Company makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -->
<Head>
<Title>Hashed Associative Container</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
	ALINK="#ff0000"> 
<IMG SRC="CorpID.gif" 
     ALT="SGI" HEIGHT="43" WIDTH="151"> 
<!--end header-->
<BR Clear>
<H1>Hashed Associative Container</H1>

<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "containers.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
<TD Align=right><Img src = "concept.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: containers</TD>
<TD Align=right VAlign=top><b>Component type</b>: concept</TD>
</TR>
</Table>

<h3>Description</h3>
A Hashed Associative Container is an <A href="AssociativeContainer.html">Associative Container</A> whose
implementation is a hash table. <A href="#1">[1]</A> The elements of a Hashed
Associative Container are not guaranteed to be in any meaningful
order; in particular, they are not sorted.  The worst case complexity
of most operations on Hashed Associative Containers is linear in the
size of the container, but the average case complexity is constant
time; this means that for applications where values are simply stored
and retrieved, and where ordering is unimportant, Hashed Associative
Containers are usually much faster than <A href="SortedAssociativeContainer.html">Sorted Associative
Containers</A>.
<h3>Refinement of</h3>
<A href="AssociativeContainer.html">Associative Container</A>
<h3>Associated types</h3>
The following new types are introduced, in addition to the types defined in the
<A href="AssociativeContainer.html">Associative Container</A> requirements. 
<Table border>
<TR>
<TD VAlign=top>
Hash function
</TD>
<TD VAlign=top>
<tt>X::hasher</tt>
</TD>
<TD VAlign=top>
A type that is a model of <A href="HashFunction.html">Hash Function</A>.  <tt>X::hasher</tt>'s argument
   type must be <tt>X::key_type</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Key equal
</TD>
<TD VAlign=top>
<tt>X::key_equal</tt>
</TD>
<TD VAlign=top>
A <A href="BinaryPredicate.html">Binary Predicate</A> whose argument type is <tt>X::key_type</tt>.  An
   object of type <tt>key_equal</tt> returns <tt>true</tt> if its arguments are
   the same key, and <tt>false</tt> otherwise.  <tt>X::key_equal</tt> must be
   an equivalence relation.  
</TD>
</tr>
</table>
<h3>Notation</h3>
<Table>
<TR>
<TD VAlign=top>
<tt>X</tt>
</TD>
<TD VAlign=top>
A type that is a model of Hashed Associative Container
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>a</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>t</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::value_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>k</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::key_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>p</tt>, <tt>q</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::iterator</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>n</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::size_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>h</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::hasher</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>c</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X::key_equal</tt>
</TD>
</tr>
</table>
<h3>Definitions</h3>
A <i>hash function</i> for a Hashed Associative Container <tt>X</tt> is a
<A href="UnaryFunction.html">Unary Function</A> whose argument type is <tt>X::key_type</tt> and whose
return type is <tt>size_t</tt>.  A hash function must be deterministic (that
is, it must always return the same value whenever it is called with
the same argument), but return values of the hash function should be
as uniform as possible: ideally, no two keys will hash to the same
value.  <A href="#2">[2]</A>
<P>
Elements in a Hashed Associative Container are organized into
<i>buckets</i>.  A Hashed Associative Container uses the value of the
hash function to determine which bucket an element is assigned to.
<P>
The number of elements in a Hashed Associative Container divided by
the number of buckets is called the <i>load factor</i>.  A Hashed
Associative Container with a small load factor is faster than one with
a large load factor.
<h3>Valid expressions</h3>
In addition to the expressions defined in <A href="AssociativeContainer.html">Associative Container</A>,
the following expressions must be valid.
<Table border>
<TR>
<TH>
Name
</TH>
<TH>
Expression
</TH>
<TH>
Type requirements
</TH>
<TH>
Return type
</TH>
</TR>
<TR>
<TD VAlign=top>
Default constructor
</TD>
<TD VAlign=top>
<pre>
X()
X a;
</pre>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Constructor with bucket count
</TD>
<TD VAlign=top>
<pre>
X(n)
X a(n);
</pre>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Constructor with hash function
</TD>
<TD VAlign=top>
<pre>
X(n, h)
X a(n, h);
</pre>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Constructor with key equal
</TD>
<TD VAlign=top>
<pre>
X(n, h, k)
X a(n, h, k);
</pre>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Hash function
</TD>
<TD VAlign=top>
<tt>a.hash_funct()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>X::hasher</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Key equal
</TD>
<TD VAlign=top>
<tt>a.key_eq()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>X::key_equal</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase key
</TD>
<TD VAlign=top>
<tt>a.erase(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>size_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase element
</TD>
<TD VAlign=top>
<tt>a.erase(p)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase range
</TD>
<TD VAlign=top>
<tt>a.erase(p, q)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Find
</TD>
<TD VAlign=top>
<tt>a.find(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>iterator</tt> if <tt>a</tt> is mutable, otherwise <tt>const_iterator</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Count
</TD>
<TD VAlign=top>
<tt>a.count(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>size_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Equal range
</TD>
<TD VAlign=top>
<tt>a.equal_range(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>pair&lt;iterator, iterator&gt;</tt> if <tt>a</tt> is mutable, otherwise
   <tt>pair&lt;const_iterator, const_iterator&gt;</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Bucket count
</TD>
<TD VAlign=top>
<tt>a.bucket_count()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>X::size_type</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Resize
</TD>
<TD VAlign=top>
<tt>a.resize(n)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
<tt>void</tt>
</TD>
</tr>
</table>
<h3>Expression semantics</h3>
<Table border>
<TR>
<TH>
Name
</TH>
<TH>
Expression
</TH>
<TH>
Precondition
</TH>
<TH>
Semantics
</TH>
<TH>
Postcondition
</TH>
</TR>
<TR>
<TD VAlign=top>
Default constructor
</TD>
<TD VAlign=top>
<pre>
X()
X a;
</pre>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Creates an empty container, using <tt>hasher()</tt> as the hash function
   and <tt>key_equal()</tt> as the key equality function.
</TD>
<TD VAlign=top>
The size of the container is <tt>0</tt>.  The bucket count is an
   unspecified default value.  The hash function is <tt>hasher()</tt>, and
   the key equality function is <tt>key_equal()</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Constructor with bucket count
</TD>
<TD VAlign=top>
<pre>
X(n)
X a(n);
</pre>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Creates an empty container with at least <tt>n</tt> buckets, using
   <tt>hasher()</tt> as the hash function and <tt>key_equal()</tt> as the key 
   equality function.
</TD>
<TD VAlign=top>
The size of the container is <tt>0</tt>.  The bucket count is
   greater than or equal to <tt>n</tt>.  The hash function is <tt>hasher()</tt>, and
   the key equality function is <tt>key_equal()</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Constructor with hash function
</TD>
<TD VAlign=top>
<pre>
X(n, h)
X a(n, h);
</pre>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Creates an empty container with at least <tt>n</tt> buckets, using
   <tt>h</tt> as the hash function and <tt>key_equal()</tt> as the key 
   equality function.
</TD>
<TD VAlign=top>
The size of the container is <tt>0</tt>.  The bucket count is
   greater than or equal to <tt>n</tt>.  The hash function is <tt>h</tt>, and
   the key equality function is <tt>key_equal()</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Constructor with key equal
</TD>
<TD VAlign=top>
<pre>
X(n, h, k)
X a(n, h, k);
</pre>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Creates an empty container with at least <tt>n</tt> buckets, using
   <tt>h</tt> as the hash function and <tt>k</tt> as the key 
   equality function.
</TD>
<TD VAlign=top>
The size of the container is <tt>0</tt>.  The bucket count is
   greater than or equal to <tt>n</tt>.  The hash function is <tt>h</tt>, and
   the key equality function is <tt>k</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Hash function
</TD>
<TD VAlign=top>
<tt>a.hash_funct()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns the hash function used by <tt>a</tt>.
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Key equal
</TD>
<TD VAlign=top>
<tt>a.key_eq()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns the key equal function used by <tt>a</tt>.
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase key
</TD>
<TD VAlign=top>
<tt>a.erase(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Destroys all elements whose key is the same as <tt>k</tt>, and removes
   them from <tt>a</tt>.  <A href="#2">[2]</A>  The return value is the number of elements that
   were erased, <i>i.e.</i> the old value of <tt>a.count(k)</tt>.
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is decremented by <tt>a.count(k)</tt>.
   <tt>a</tt> contains no elements with key <tt>k</tt>.  
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase element
</TD>
<TD VAlign=top>
<tt>a.erase(p)</tt>
</TD>
<TD VAlign=top>
<tt>p</tt> is a dereferenceable iterator in <tt>a</tt>.
</TD>
<TD VAlign=top>
Destroys the element pointed to by <tt>p</tt>, and removes it from <tt>a</tt>.
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is decremented by 1.
</TD>
</TR>
<TR>
<TD VAlign=top>
Erase range
</TD>
<TD VAlign=top>
<tt>a.erase(p, q)</tt>
</TD>
<TD VAlign=top>
<tt>[p, q)</tt> is a valid range in <tt>a</tt>.
</TD>
<TD VAlign=top>
Destroys the elements in the range <tt>[p,q)</tt> and removes them from
   <tt>a</tt>. 
</TD>
<TD VAlign=top>
<tt>a.size()</tt> is decremented by the distance from <tt>i</tt> to <tt>j</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Find
</TD>
<TD VAlign=top>
<tt>a.find(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns an iterator pointing to an element whose key is the same
   as <tt>k</tt>, or <tt>a.end()</tt> if no such element exists.
</TD>
<TD VAlign=top>
Either the return value is <tt>a.end()</tt>, or else the return value has
   a key that is the same as <tt>k</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Count
</TD>
<TD VAlign=top>
<tt>a.count(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns the number of elements in <tt>a</tt> whose keys are the same as <tt>k</tt>.
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Equal range
</TD>
<TD VAlign=top>
<tt>a.equal_range(k)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns a pair <tt>P</tt> such that <tt>[P.first, P.second)</tt> is a range
   containing all elements in <tt>a</tt> whose keys are the same as <tt>k</tt>. <A href="#3">[3]</A>
   If no elements have the same key as <tt>k</tt>, the return value is an empty
   range.
</TD>
<TD VAlign=top>
The distance between <tt>P.first</tt> and <tt>P.second</tt> is equal to
   <tt>a.count(k)</tt>.  If <tt>p</tt> is a dereferenceable iterator in <tt>a</tt>, then
   either <tt>a</tt> lies in the range <tt>[P.first, P.second)</tt>, or else
   <tt>*a</tt> has a key that is not the same as <tt>k</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Bucket count
</TD>
<TD VAlign=top>
<tt>a.bucket_count()</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Returns the number of buckets in <tt>a</tt>.
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
Resize
</TD>
<TD VAlign=top>
<tt>a.resize(n)</tt>
</TD>
<TD VAlign=top>
&nbsp;
</TD>
<TD VAlign=top>
Increases the bucket count of <tt>a</tt>.
</TD>
<TD VAlign=top>
The bucket count of <tt>a</tt> will be at least <tt>n</tt>.  All iterators pointing
   to element in <tt>a</tt> will remain valid. <A href="#3">[3]</A>
</TD>
</tr>
</table>
<h3>Complexity guarantees</h3>
The default constructor, constructor with bucket count,
constructor with hash function, and constructor 
with key equal, are all amortized constant time.
<P>
Hash Function and Key Equal are amortized constant time.
<P>
Average complexity for Erase Key is <tt>O(count(k))</tt>.  Worst case is
linear in the size of the container.
<P>
Erase Element is amortized constant time.
<P>
Average complexity for Erase Range is <tt>O(N)</tt>, where <tt>N</tt> is the length
of the range being erased.  Worse case is linear in the size of the
container.
<P>
Average complexity for Find is constant time.  Worst case is linear in
the size of the container.
<P>
Average complexity for Equal Range is <tt>O(count(k))</tt>.  Worst case is
linear in the size of the container.
<P>
Average complexity for Count is <tt>O(count(k))</tt>.  Worst case is linear
in the size of the container.
<P>
Bucket Count is amortized constant time.
<P>
Resize is linear in the size of the container.
<h3>Invariants</h3>
<h3>Models</h3>
<UL>
<LI>
<tt><A href="hash_set.html">hash_set</A></tt>
<LI>
<tt><A href="hash_map.html">hash_map</A></tt>
<LI>
<tt><A href="hash_multiset.html">hash_multiset</A></tt>
<LI>
<tt><A href="hash_multimap.html">hash_multimap</A></tt>
</UL>
<h3>Notes</h3>
<P><A name="1">[1]</A>
There is an extensive literature dealing with hash tables.  See,
for example, section 6.4 of Knuth.  (D. E. Knuth, <i>The Art of Computer
Programming.  Volume 3: Sorting and Searching</i>.
Addison-Wesley, 1975.)
<P><A name="2">[2]</A>
If the hash function is poor (that is, if many different keys hash
to the same value) then this will hurt performance.  The worst
case is where every key hashes to the same value; in this case, run-time
complexity of most Hashed Associative Container operations will be
linear in the size of the container.
<P><A name="3">[3]</A>
Resizing does not invalidate iterators; however, it does not
necessarily preserve the ordering relation between iterators.
That is, if <tt>i</tt> and <tt>j</tt> are iterators that point into a 
Hashed Associative Container such that <tt>i</tt> comes immediately
before <tt>j</tt>, then there is no guarantee that <tt>i</tt> will still come
immediately before <tt>j</tt> after the container is resized.  The only
guarantee about about the ordering of elements is the contiguous
storage invariant: elements with the same key are always adjacent
to each other.
<h3>See also</h3>
<A href="AssociativeContainer.html">Associative Container</A>, <A href="SortedAssociativeContainer.html">Sorted Associative Container</A>,
<A href="UniqueHashedAssociativeContainer.html">Unique Hashed Associative Container</A>, 
<A href="MultipleHashedAssociativeContainer.html">Multiple Hashed Associative Container</A>, 

<!--start footer--> 
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" 
        ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif" 
        HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright &copy; 
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML> 
